#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>
#include <ctime>
#include<stack>

using namespace std;

void display(vector<int> & vct){
    return;
    for(auto a:vct){
        cout << a<<' ';
    }
    cout << endl;
}

// rand
class RandInt{
    vector <int> arr;
    vector <int> arr_good;
    vector <int> arr_bad;
    int t;
public:
    RandInt(int sz,int m1,int m2){
        while (sz--)
        {
            t = rand() % (m2 - m1) + m1;
            arr.push_back(t);
            arr_good.push_back(t);
            arr_bad.push_back(t);
        }
        sort(arr_good.begin(),arr_good.end(),less<int>());
        sort(arr_bad.begin(),arr_bad.end(),greater<int>());
        cout <<"array:";display(arr);
        cout <<"good:";display(arr_good);
        cout <<"bad:";display(arr_bad);
    }

    vector<int> getArr(){
        return arr;
    }
    vector<int> getGood(){
        return arr_good;
    }
    vector<int> getBad(){
        return arr_bad;
    }
};


// sort test
class Sort{
    vector<int> arr_normal;
    vector<int> arr_good;
    vector<int> arr_bad;
    clock_t clock_begin;
    clock_t clock_end;
public:
    Sort(vector<int> a,vector<int> b,vector<int> c){
        arr_normal = a;
        arr_good = b;
        arr_bad = c;
    }
    // test
    void test(){
        clock_begin = clock(); 
        _sort(arr_normal);
        clock_end = clock(); 
        cout << "normal times:" << clock_end - clock_begin <<" ms"<< endl;
        clock_begin = clock(); 
        _sort(arr_good);
        clock_end = clock(); 
        cout << "good times:" << clock_end - clock_begin <<" ms"<< endl;
        clock_begin = clock(); 
        _sort(arr_bad);
        clock_end = clock(); 
        cout << "bad times:" << clock_end - clock_begin <<" ms" << endl;

    }

    // reload func
    virtual  void _sort(vector<int>& a){

    }
};



class QuickSort :public Sort{
    public:
    QuickSort(vector<int> a,vector<int> b,vector<int> c):Sort(a,b,c){
        
    }

    void _sort(vector<int> & array){
        sort(0,array.size() - 1,array);
    }

    void sort(int left,int right,vector<int> & arr){
        if(left >= right) return;
        int i,j,temp;
        i = left;j = right;
        temp = arr[left];
        
        while ( i != j)
        {
            while ( arr[j] >= temp && i < j){
                j--;
            }
            while (arr[i] <= temp && i < j)
            {
                i++;
            }
            if( i < j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        
        if(left != i){
            arr[left] = arr[i];
            arr[i] = temp;
        }
        sort(left ,i - 1,arr);
        sort(i + 1 , right,arr);
    }
};




class QuickSortNormal:public Sort{
    public:
    QuickSortNormal(vector<int> a,vector<int> b,vector<int> c):Sort(a,b,c){
        
    }

    void _sort(vector<int> & array){
        sort(0,array.size() - 1,array);
    }

    void sort(int left,int right,vector<int> & arr){
        if(left >= right) return;
        int i,j,temp;
        i = left;j = right;
        temp = arr[left];
        
        while ( i != j)
        {
            while ( arr[j] >= temp && i < j){
                j--;
            }
            while ( arr[i] <= temp && i < j)
            {
                i++;
            }
            if(i < j){
                
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        
        if(left != i){

            arr[left] = arr[i];
            arr[i] = temp;
        }
        sort(left ,i - 1,arr);
        sort(i + 1 , right,arr);
    }
};


class QuickSortNormalRand:public Sort{
    public:
    QuickSortNormalRand(vector<int> a,vector<int> b,vector<int> c):Sort(a,b,c){
        
    }

    void _sort(vector<int> & array){
        sort(0,array.size() - 1,array);
    }

    void sort(int left,int right,vector<int> & arr){
        if(left >= right) return;
        int i,j,temp,R;
        R = rand() % (right - left) + left;
        swap(arr[left],arr[R]);
        
        i = left;j = right;
        temp = arr[left];
        
        while (i != j)
        {
            while (arr[j] >= temp && i < j){
                j--;
            }
            while  (arr[i] <= temp && i < j)
            {
                i++;
            }
            if(i < j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        
        if(left != i){
            arr[left] = arr[i];
            arr[i] = temp;
        }
        sort(left ,i - 1,arr);
        sort(i + 1 , right,arr);
    }
};


class QuickSortNormalWithStack:public Sort{
    public:
    stack<pair<int,int>> st;
    QuickSortNormalWithStack(vector<int> a,vector<int> b,vector<int> c):Sort(a,b,c){
        
    }

    void _sort(vector<int> & array){
        while(!st.empty())st.pop();
        sort(array);
    }

    void sort(vector<int> & arr){
        st.push(pair<int,int>(0,arr.size() - 1));
        pair<int,int> p;
        int left,right,i,j,temp;
        while(!st.empty()){
            p = st.top();st.pop();
            left = p.first;right = p.second;
            if (left >= right) continue;
            i = left; j = right; temp = arr[left];
            while (i != j)
            {
                while (arr[j] >= temp && i < j)j--;
                while (arr[i] <= temp && i < j)i++;
                swap(arr[i],arr[j]);
            }
            swap(arr[left],arr[i]);
            st.push(pair<int,int>(left,i - 1));
            st.push(pair<int,int>(i +1 ,right));
        }
    }
};

class QuickSortNormalWithStackAndRand:public Sort{
    public:
    stack<pair<int,int>> st;
    QuickSortNormalWithStackAndRand(vector<int> a,vector<int> b,vector<int> c):Sort(a,b,c){
        
    }

    void _sort(vector<int> & array){
        while(!st.empty())st.pop();
        sort(array);
    }

    void sort(vector<int> & arr){
        st.push(pair<int,int>(0,arr.size() - 1));
        pair<int,int> p;
        int left,right,i,j,temp,R;
        while(!st.empty()){
            p = st.top();st.pop();
            left = p.first;right = p.second;
            if (left >= right) continue;
            R = rand() % (right - left) + left;
            swap(arr[left],arr[R]);
            i = left; j = right; temp = arr[left];
            
            while (i != j)
            {
                while (arr[j] >= temp && i < j)j--;
                while (arr[i] <= temp && i < j)i++;
                swap(arr[i],arr[j]);
            }
            swap(arr[left],arr[i]);
            st.push(pair<int,int>(left,i - 1));
            st.push(pair<int,int>(i +1 ,right));
        }
    }
};



int main(){
    while(1){
        int t;
        cout << "Input Array Size:"<< endl;
        cin >> t;
        if (t == 0) break;
        RandInt * r = new RandInt(t,100,1000);
        while(1){
            QuickSort q1(r->getArr(),r->getGood(),r->getBad());
            QuickSortNormal q2(r->getArr(),r->getGood(),r->getBad());
            QuickSortNormalRand q3(r->getArr(),r->getGood(),r->getBad());
            QuickSortNormalWithStack q4(r->getArr(),r->getGood(),r->getBad());
            QuickSortNormalWithStackAndRand q5(r->getArr(),r->getGood(),r->getBad());
            cout << "test QuickSort"<<endl<<endl;
            q1.test();
            cout << "test QuickSortNormal"<<endl<<endl;
            q2.test();
            cout << "test QuickSortNormalRand"<<endl<<endl;
            q3.test();
            cout << "test QuickSortNormalWithStack"<<endl<<endl;
            q4.test();
            cout << "test QuickSortNormalWithStackAndRand"<<endl<<endl;
            q5.test();
            cout <<"input any to test again!"<<endl;
            cin >> t;
            if (t == 0) break;
        }
        

    }
    return 0;
}
